package _02_并查集;
/*
    QuickUnion -> 基于rank - 路径减半
 */
public class QuickUnion_Rank_PH extends QuickUnion_Rank{
    public QuickUnion_Rank_PH(int capacity) {
        super(capacity);
    }

    /*
        使路径上每隔一个节点就指向其祖父节点
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        while(v!=parents[v]){
            parents[v] = parents[parents[v]];
            v = parents[v];
        }
        return v;
    }
}
